package exam.test7;

import java.util.ArrayList;
import java.util.List;

public class Solution2 {

//    public static void main(String[] args) {
//        Solution solution = new Solution();
////        int columnCount = 2;
////        int rowCount = 2;
////        int[][] mat = {{5, 1}, {4, 5}};
//
//        int columnCount = 3;
//        int rowCount = 3;
//        int[][] mat = {{6, 1, 6}, {4, 5, 7}, {2, 3, 8}};
//
//        int ret = solution.maxOfMinElevation(columnCount, rowCount, mat);
//        System.out.println(ret);
//    }

    public int maxOfMinElevation(int columnCount, int rowCount, int[][] mat) {
        if (columnCount <= 1 || rowCount <= 1) {
            return 0;
        }

        List<List<Integer>> pathList = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        path.add(mat[0][0]);
        maxOfMinElevationHelper(pathList, mat, path, 0, 0);
//        System.out.println("Find path = " + pathList);

        List<Integer> minimumList = new ArrayList<>();
        int max = 0;
        for (List<Integer> pathTmp : pathList) {
            for (int i = 0; i < pathTmp.size() - 1; i++) {
                if (pathTmp.get(i) > pathTmp.get(i+1)) {
                    minimumList.add(pathTmp.get(i + 1));
                    if (max <= pathTmp.get(i + 1)) {
                        max = pathTmp.get(i + 1);
                    }
                }
            }
        }
//        System.out.println("Minimum  elevation = " + minimumList);
//        System.out.println("Maximum of minimum  elevation = " + max);

        return max;
    }

    private void maxOfMinElevationHelper(List<List<Integer>> pathList, int[][] mat, List<Integer> path, int currentColumnIndex, int currentRowIndex) {
        if (currentColumnIndex == mat[0].length - 1 && currentRowIndex == mat.length- 1) {
            pathList.add(new ArrayList<>(path));
            return;
        }

        if (currentColumnIndex < mat[0].length - 1) {
            path.add(mat[currentRowIndex][currentColumnIndex + 1]);
            maxOfMinElevationHelper(pathList, mat, path, currentColumnIndex + 1, currentRowIndex);
            path.remove(path.size()-1);
        }

        if (currentRowIndex < mat.length - 1) {
            path.add(mat[currentRowIndex + 1][currentColumnIndex]);
            maxOfMinElevationHelper(pathList, mat, path, currentColumnIndex, currentRowIndex + 1);
            path.remove(path.size()-1);
        }
    }
}
